//
// Created by ASUS on 2024/3/20.
//

#include <bits/stdc++.h>
using namespace std;


int _multi_dp_binary(vector<int>& weight, vector<int>& value, vector<int>&cnt ,int target){
	int n=weight.size();
	//二进制拆分
	vector<int> ww,vv;
	for(int i=0;i<n;i++){
		for(int j=1;j<=cnt[i];j<<=1){
			ww.push_back(j*weight[i]);
			vv.push_back(j*value[i]);
			cnt[i]-=j;
		}
		if(cnt[i]){
			vv.push_back(cnt[i]*weight[i]);
			ww.push_back(cnt[i]*value[i]);
		}
	}
	//0-1背包dp
	vector<int> f(target+1,0);
	for(int i=0;i<ww.size();i++){
		for(int j=target;j>=ww[i];j--){
			f[j]=max(f[j],f[j-ww[i]]+vv[i]);
		}
	}
	return f[target];
}